1. Field of the Invention
The present invention relates generally to a data compression method and system. More specifically, the invention relates to a lossless type data compression method employing dictionary system suitable for a character generator for a game machine and so forth.
2. Description of the Related Art
Conventionally, various data compression methods have been developed for reduction of necessary capacity of storage devices in data processing systems and for improvement of data transmission efficiency. The data compression method may be generally divided into lossy type and lossless type in the viewpoint of capability of bidirectional coding.
The lossy type data compression method is nonreversible coding system. JPEG (Joint Photographic Coding Expert Group), MPEG (Moving Picture Image Coding Expert Group), H.261 for PMS (Picture-phone Meeting Service) or picture telephone and so forth are internationally standardized systems of this lossy type data compression. The lossy type data compression is advantage for high compression rate, i.e. approximately 1/50 to 1/1000 while loss of information amount is caused.
On the other hand, the lossless type data compression method is a reversible data coding system. This type of data compression system generally holds data compression rate approximately 1/2 and thus cannot achieve high compression rate as achieved by the lossy type data compression method. However, the lossless type data compression method is advantageous for capability of encoding and decoding without loosing an original data. Run Length coding, Huffman coding, Arithmetic coding, LZ (Lemple-Ziv) system and so forth are typical standardized systems in the lossless type data compression methods.
The run length coding system is the simplest lossless type coding system. The system utilizes the fact that probability of appearance is differentiated depending upon the value of the run length. Therefore, by assigning shorter code for the run length having higher probability, data compression is achieved. This coding system has been employed in CD-I (Compact Disc-Interface), Video for Windows (Trademark: Microsoft) and so forth.
Huffman coding system is a data compression system primarily used in the field of image processing. MH (Modified Huffman) coding of G3 standard facsimile and so forth are application of the Huffman coding.
It should be noted that JPEG, MPEG, or H.261 also employs Huffman coding. However, since these method use DCT (Discrete Cosine Transfer) in preparatory process, they are classified as lossy type.
Arithmetic coding system is used in JBIG (Joint Bi-level Image Coding Expert Group) which is next age coding system in the facsimile. The JBIEG may handle redundant data stream which cannot be handled by Huffman coding system, by unitary compression based on probability of occurrence of strings. Thus, the JBIEG realizes optimal data compression in view of information entropy.
In general. LZ system is a data compression system which performs data compression detecting repetition of strings. The LZ system is applied for a data compression tool for personal computers or for data backup cartridge tape recording apparatus and other products.
The LZ system generally includes LZ77 system, Ziv J. and Lempel, A. "A Universal Algorithm for Sequential Data Compression", IEEE Transaction on Information Theory, vol. IT-23, No. 3, pp 337-343, September, 1997 and LZ78 system, Ziv, J. and Lempel, A. "Compression of Individual Sequences via Variable Rate Coding" IEEE Translation on Information Theory, vol IT-24, No. 5, pp 530 to 536, September 1978. The former LZ77 system is also disclosed in U.S. Pat. Nos. 5,003,307 and 5,016,009. The later LZ78 system is also disclosed in U.S. Pat. Nos. 4,558,302 and 4,814,746. Algorithms of LZ77 and LZ78 systems are in common at the point where the currently objective string and processed strings are compared and the longest matching string is obtained through the comparison. However, LZ77 stores the processed strings in a buffer and takes means to handled the processed data as if the processed data in the buffer is slide on the input data stream. On the other hand, the LZ78 system employs means for assigning dedicated codes for processed strings and registering the codes in dictionary style.
As a result, in comparison of LZ77 and LZ78 systems in terms of function, LZ77 system is superior than the LZ78 system in terms of compression rate, and LZ78 system superior than the LZ77 system in terms of data processing speed.
On the other hand, in the field of gate machine, requirement for high level image expression is progressively growing. In the commercial gate machine, image expression utilizing three-dimensional CG (computer graphics) has been employed. The trend is extending to home use television game machines and multimedia systems. Thus, development for data processing systems capable of such high level image expression are progressed.
Complication of image expression causes increasing of data amount. Therefore, a demand for lossless type data compression method having high compression rate and capable of high speed encoding and decoding, is growing.
Particularly, in case of the game machine, unless the display screen reacts to operation of a button on a control pad by a user within 1/60 to 1/30 seconds (corresponding to display period of one or two field of color television signal), game becomes less interesting. Therefore, it is inherent to achieve both of the high compression rate and high speed encoding and decoding.
In this sense, the above-mentioned the LZ system (particularly LZ78) and LHA system, in which the LZ system and Huffman coding system may be said as suitable data compression method as data compression method.
However, in case of the LZ system, since respective of the individual strings as object for compression have variable, and algorithm for compression and decompression is complicate, the data processing procedure may contain large number of steps and the hardware construction may become complicate.
On the other hand, in the character generator in the game machine, a relatively small data block is handled. In the conventional data compression method, compression becomes impossible or at least insufficient in compression.
Also, the data block of the character generator in the game machine, in has a tendency to have high probability of occurrence of the same string, and not to cause significant variation of number of the data blocks corresponding to variation mode of the characters.